package try01;

import java.util.Arrays;

public class UniquePathsII {

	public void tester() {
		int [][] a = {{1,2},{3,4},{5,6}};
		System.out.println(minPathSum(a));
	}
	
	public int minPathSum(int[][] grid) {
        if(grid[grid.length-1][grid[0].length-1] == 1) return 0;
        
        for(int i = grid.length - 1 ; i >= 0 ; i--) {
            for(int j = grid[0].length - 1 ; j >= 0 ; j--) {
                if(i+1 == grid.length && j+1 == grid[0].length) {
                    
                }
                else if(i+1 == grid.length) {
                    grid[i][j] = grid[i][j] + grid[i][j+1];
                }
                else if(j+1 == grid[0].length) {
                    grid[i][j] = grid[i][j] + grid[i+1][j];
                }
                else {
                    if(grid[i+1][j] > grid[i][j+1]) {
                    	grid[i][j] = grid[i][j] + grid[i][j+1];
                    }
                    else {
                    	grid[i][j] = grid[i][j] + grid[i+1][j];
                    }
                        
                }
                
                System.out.println(grid[0][0] + " "+grid[0][1]);
                System.out.println(grid[1][0] + " "+grid[1][1]);
                System.out.println(grid[2][0] + " "+grid[2][1]);
                System.out.println();
            }
        }
        
        return grid[0][0];
    }
	
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        cache = obstacleGrid;
        if(cache.length == 0) return 1;
        
        for(int i = 0 ; i < cache.length ; i++) {
            for(int j = 0 ; j < cache[0].length ; j++) {
                if(cache[i][j] == 1) cache[i][j] = -1;
                if(cache[i][j] == 0) cache[i][j] = -2;
            }
        }
        
        rt = cache.length - 1;
        ct = cache[0].length - 1;
        
        return up(0, 0);
    }
    
    int [][] cache;
    int rt = 0, ct = 0;
    
    public int up(int r, int c) {
        if(cache[r][c] == -1) return 0;
        
        if(cache[r][c] != -2) return cache[r][c];
        
        if(r == rt && c == ct) return 1;
        if(r == rt) return up(r, c+1);
        if(c == ct) return up(r+1, c);

        cache[r][c] = up(r+1, c) + up(r, c+1);
        System.out.println(r+" "+c+" "+cache[r][c]);
        
        return cache[r][c];
    }
    
    public int uniquePathsWithObstacles2(int[][] grid) {
        if(grid.length == 0) return 0;
        if(grid[0][0] == 1) return 0;
        if(grid[grid.length-1][grid[0].length-1] == 1) return 0;
        
        for(int i = grid.length - 1 ; i >= 0 ; i--) {
            for(int j = grid[0].length - 1 ; j >= 0 ; j--) {
                if(grid[i][j] == 1) {
                    grid[i][j] = 0;
                }
                else if(i+1 == grid.length && j+1 == grid[0].length) {
                    grid[i][j] = 1;
                }
                else if(i+1 == grid.length) {
                    grid[i][j] = grid[i][j+1];
                }
                else if(j+1 == grid[0].length) {
                    grid[i][j] = grid[i+1][j];
                }
                else {
                    grid[i][j] = grid[i+1][j] + grid[i][j+1];
                }
                
//                System.out.println(grid[0][0] + " "+grid[0][1]);
//                System.out.println(grid[1][0] + " "+grid[1][1]);
//                System.out.println(grid[2][0] + " "+grid[2][1]);
//                System.out.println();
            }
        }
        
        return grid[0][0];
    }
}
